1849D - Array Painting - CodeForces Solution

//It's better to have sex than to do questions
#include<bits/stdc++.h>
#include<string>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<stack>
#define fi first
#define se second
#define ll long long
#define ull unsigned long long
using namespace std;
const int N=2e5+5;
const ll md=1e9+7;
const ll inf=1e18;
const ll eps=1e-9;
const double E=2.718281828;
int n,a[N],vis[N];
vector<int>bit[3];
void solve(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		vis[i]=0;
		bit[a[i]].push_back(i);
	}
	int ans=0;
	for(int v:bit[2]){
		int l=v-1,r=v+1;
		if(vis[v])continue;
		vis[v]=2;
		ans+=1;
		while(!vis[l]&&a[l]!=0&&l>=1){
			vis[l]=2;
			l--;
		}
		while(!vis[r]&&a[r]!=0&&r<=n){
			vis[r]=2;
			r++;
		}
		vis[l]=vis[r]=2;
	}
	for(int v:bit[1]){
		int l=v-1,r=v+1;
		if(vis[v])continue;
		vis[v]=1;
		ans+=1;
		while(!vis[l]&&a[l]!=0&&l>=1){
			vis[l]=1;
			l--;
		}
		while(!vis[r]&&a[r]!=0&&r<=n){
			vis[r]=1;
			r++;
		}
//		cout<<l+1<<" "<<r-1<<endl;
	}
//	int cnt[2]={0,0},all=0;
	for(int v:bit[0]){
		if(!vis[v]){
//			cout<<v<<endl;
			if(vis[v-1]==1){
//				cout<<"front"<<endl;
				vis[v]=3;
			}else if(vis[v+1]==1){
				vis[v]=1;
				int j=v;
				while(vis[j]==1&&j<=n){
					vis[j]=2;
					j++;
				}
			}
		}
	}
	for(int i=1;i<=n;i++){
		if(!vis[i]){
			ans++;
		}
	}
	cout<<ans<<endl;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t=1;
//	cin>>t;
	while(t--){
		solve();
	}

}